This disclosure relates generally to digital animation. More particularly, but not by way of limitation, this disclosure relates to techniques for providing animation capability to a system with restricted cache memory.
A polygon mesh is a collection of vertices, edges and faces that define the shape of a polyhedral object in three-dimensional (3D) computer graphics and solid modeling. polyhedral faces often consist of triangles (triangle mesh), quadrilaterals, or other simple convex polygons since this simplifies rendering, but may also be composed of more general concave polygons, or polygons with holes. A vertex is a position and, possibly, other information such as color, a normal vector and texture coordinates. An edge is a connection between two vertices. A face is a closed set of edges in which a triangle face has three edges, and a quad has four edges and so on. A polygon is a coplanar set of faces.
Mathematically a polygonal mesh may be considered an unstructured grid, or undirected graph with the additional properties of geometry, shape and topology. Polygonal meshes may be represented in a variety of ways, using different methods to store the vertex, edge and face data. Illustrative representational schemes include:                1. Face-vertex meshes: a simple list of vertices, and a set of polygons that point to the vertices it uses;        2. Winged-edge meshes, in which each edge points to two vertices, two faces, and the four (clockwise and counter clockwise) edges that touch them;        3. Half-edge meshes, are similar to winged-edge meshes except that only half the edge traversal information is recorded;        4. Quad-edge meshes, store edges, half-edges, and vertices without any reference to polygons which are implicit in the representation, and may be found by traversing the structure;        5. Corner-tables, store vertices in a predefined table such that traversing the table implicitly defines polygons; and        6. Vertex-vertex meshes represents only vertices, which point to other vertices (both the edge and face information is implicit in the representation).        
Three-dimensional mesh sequences may be used to represent animations in the form of deforming meshes. Deformation transfer (DT) and animation warping are two typical techniques used to recreate meaningful mesh animations from a given mesh sequence. Standard morphing operations generally entail morphing every vertex of a target object's mesh representation at each frame of an animation. Even small meshes may be comprised of from several thousand to more than ten-thousand vertices. In systems having limited computational power and/or limited memory, it may not be possible to perform morphing operations in a manner that provides a satisfactory user experience. For example, even small meshes can consume a large amount of memory. Consider a 10,000 vertex mesh where each vertex includes position (x, y and z values), color (R, G and B values), a normal vector (x, y and z values), and texture coordinates (e.g., an address) for a total of about 50 bytes. Such a mesh requires 500,000 bytes of memory to store for every update operation. When frame update rates are 30 frames-per-second (fps), this translates into approximately 15 MB/sec (megabytes-per-second) of memory bandwidth. When frame update rates are 60 fps, this translates into approximately 30 MB/sec of memory bandwidth. In systems that have less powerful processors (e.g., central processor units) or limited to no cache memory, these memory bandwidths may not be available.